Lát cắt (lý thuyết đồ thị)

Trong lý thuyết đồ thị, một lát cắt là một cách phân chia tập hợp các đỉnh của một đồ thị thành hai tập hợp con không giao nhau. Tập hợp cắt của lát cắt là tập hợp các cạnh có hai đầu nằm ở hai tập hợp con khác nhau. Một cạnh của đồ thị là bị cắt nếu nó nằm trong tập hợp cắt.Trong một đồ thị vô hướng không trọng số, kích thước của một lát cắt chính là số cạnh bị cắt. Trong đồ thị có trọng số, kích thước hay trọng số của lát cắt là tổng trọng số các cạnh bị cắt.Trong một đồ thị luồng, một lát cắt s-t là một lát cắt trong đó đỉnh phát và đỉnh thu nằm ở hai tập hợp con khác nhau, và tập hợp cắt chỉ gồm các cung từ tập hợp con chứa đỉnh phát tới tập hợp con chứa đỉnh thu. Khả năng thông qua của một lát cắt s-t được định nghĩa là tổng khả năng thông qua của các cung trong tập hợp cắt.Khái niệm lát cắt của một đồ thị cũng được dùng để chỉ tập hợp cắt thay vì phân chia của tập hợp đỉnh.